<?php

/**
 * Description of Packager
 *
 * @author user
 */
class Diff {
    private $a1;
    private $a2;
    private $ex;
    private $diff;

    public function __construct($text1, $text2) {
        if (strpos($text1, "\n") !== false) {
            $ex = "\n";
        } else {
            $chrs = count_chars($text1);
            arsort($chrs);
            $ex = array_shift(array_keys($chrs));
            $ex = chr($ex);
        }
        $this->a1 = explode($ex, $text1);
        $this->a2 = explode($ex, $text2);
        $this->ex = $ex;
        $this->diff = array();
    }
    
    public function diff() {
        $result = array();
        $a1 = $this->a1;
        $a2 = $this->a2;
        $ex = $this->ex;
        $eq = true;
        $p1 = 0;
        $p2 = 0;
        while($eq && ($p1 < count($a1)) && ($p2 < count($a2))) {
            if ($a1[$p1] == $a2[$p2]) {
                echo "$p1 == $p2<br/>\n";
                $p1++;
                $p2++;
            } else {
                $o1 = $p1;
                $o2 = $p2;
                echo "p1 = $p1; p2 = $p2<br/>\n";
                if ($this->find_eq($a1, $a2, $o1, $o2, 0, true)) {
                    echo "o1 = $o1; o2 = $o2<br/>\n";
                    if (($p2 == $o2) and (($o1-$p1) == 1)) {
                        $this->del($p1);
                        $p1++;
                        continue;
                    } elseif (($o2 - $p2) == 1) {
                        similar_text($a1[$p1+1], $a2[$p2], $st);
                        if ($st > 50) {
                            $this->del($p1);
                            $p1++;
                            continue;
                        } else {
                            $this->add($p1, $p2);
                            $p2++;
                            continue;
                        }
                    } elseif (($o1 == $p1) and ($o2>$p2)) {
                        $this->add($p1, $p2);
                        $p2++;
                        continue;
                    } elseif (($o2 - $p2) > 1) {
                        similar_text($a1[$p1], $a2[$p2], $st);
                        if ($st > 50) {
                            $this->edit($p1, $p2);
                        } else {
                            $this->del($p1);
                            $p1++;
                            continue;
                        }
                    } elseif ($o1 > $o2 and (($o1 == $p1) or ($o2 == $p1)))  {
                        $this->del($p1);
                        $p1++;
                        continue;
//                    } elseif ()
                    } else {
//                        $this->edit($p1, $p2);
                    }
                    $p1++;
                    $p2++;
                    continue;
                } else {
                    $this->edit($p1, $p2);
                }
            }
//            $p1++;
//            $p2++;
        }
        $this->add_end($p2);
        return $this->diff;
    }

    private function pos1($id) {
        $a = $this->a1;
//        var_dump($a);
        $ret = 0;
        for ($x=0; $x<$id; $x++) {
            $ret += strlen($a[$x].$this->ex);
        }
        return ++$ret;
    }

    private function pos2($id) {
        $a = $this->a2;
//        var_dump($a);
        $ret = 0;
        for ($x=0; $x<$id; $x++) {
            $ret += strlen($a[$x].$this->ex);
        }
        return ++$ret;
    }

    private function find_eq($a1, $a2, &$p1, &$p2, $br, $start = NULL) {
//        echo "branch $br [$p1, $p2](".count($a1).','.count($a2).") started<br/>\n";
        if (($p1 == count($a1)) or ($p2 == count($a2))) {
            return false;
        }
        if ($a1[$p1] == $a2[$p2]) {
//            echo "eq found at <$p1, $p2><br/>\n";
            return true;
        }

//        if ($p1-$p2 == 1) return false;
            $np = $p2+1;
//            echo "<blockquote>\n";
            if (self::find_eq($a1, $a2, $p1, $np, $br+1)) {
//                echo "</blockquote>\n";
                $p2 = $np;
                return  true;
            }
//            echo "</blockquote>\n";
        
        if ($br == 0) {
                $np = $p1+1;
//                echo "<blockquote>\n";
                if (self::find_eq($a1, $a2, $np, $p2, $br)) {
//                    echo "</blockquote>\n";
                    $p1 = $np;
                    return  true;
                }
//                echo "</blockquote>\n";
        }
        return false;
    }

    private function get_a1($start, $stop) {
        $ex = $this->ex;
        $ret = array();
        for ($start; $start < $stop; $start++) {
            $ret[] = $this->a1[$start];
        }
        return implode($ex, $ret).$ex;
    }

    private function get_a2($start, $stop) {
        $ex = $this->ex;
        $ret = array();
        for ($start; $start < $stop; $start++) {
            $ret[] = $this->a2[$start];
        }
        return implode($ex, $ret).$ex;
    }

    private function add($to, $from) {
//        echo "add <$to, $from><br/>\n";
        $pos = $this->pos2($to);
        $what = $this->get_a2($from, $from+1);
        echo "add <$to, $what><br/>\n";
        $this->diff[] = array($pos, '+', '', $what);
    }

    private function add_end($p2) {
        if ($p2 == count($this->a2)) return;
        $pos = $this->pos2(count($thos->a1));
        $what = $this->get_a2($p2, count($this->a2));
        $this->diff[] = array($pos, '+', false, $what);
    }

    private function del($from) {
        echo "del <$from><br/>\n";
        $pos = $this->pos1($from);
        $what = $this->get_a1($from, $from+1);
        $this->diff[] = array($pos, '-', $what, false);
    }

    private function edit($from, $to) {
        echo "edit <$from, $to><br/>\n";
        $pos = $this->pos1($from);
//        echo "edit $from -> $pos<br/>\n";
        $src = $this->a1[$from].$this->ex;
        $trg = $this->a2[$to].$this->ex;
        $this->diff[] = array($pos, '%', $src, $trg);
    }

    function graph() {
        if (!$this->diff) $this->diff();
        var_dump($this->diff);
        $text = implode($this->ex, $this->a1);
        $fix = 0;
        $ret = '';
        foreach($this->diff as $df) {
            $repl = '';
            if ($df[2]) {
                $repl = "</pre><del><pre>$df[2]</pre></del><pre>";
            }
            if ($df[3]) {
                $repl .= "</pre><ins><pre>$df[3]</pre></ins><pre>";
            }
            $text = substr_replace($text, $repl, $fix+$df[0]-1, strlen($df[2]));
            $fix += strlen($repl)-strlen($df[2]);
        }
        return '<pre>'.$text.'</pre>';
    }
}

?>